package 数据结构和算法.剑指offer.链表.链表中倒数第k个节点;

import 工具.动态链表生成.DynamicListUtil;
import 工具.单向节点.Node;
import 工具.打印.PrintUtil;

/**
 * 链表中倒数第k个节点
 * <p>
 * 使用双指针来解决。首先让前指针先走k步，然后双指针一起向后遍历，
 * 当头指针到结尾时，尾指针恰好就是倒数第k个节点
 */
public class Test {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        PrintUtil.println(getKthFromEnd(DynamicListUtil.createDynamicList(array), 1).getValue());
    }

    public static Node getKthFromEnd(Node head, int k) {
        Node former = head;
        Node later = head;

        for (int i = 0; i < k; ++i) {
            former = former.getNext();
        }

        while (former != null) {
            former = former.getNext();
            later = later.getNext();
        }

        return later;
    }
}
